#include<stdio.h>
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define Status int
#define TRUE 1
#define FALSE 0
#define OVERFLOW 0

//队列(Queue)是仅在表尾进行插入操作，在表头进行删除操作的线性表
//表尾即an端,称为队尾；表头即a1端，称为队头
//队列是一种先进先出(FIFO)的线性表
//插入元素称为入队; 删除元素称为出队 
//队列的存储结构为：链式队列(链队) 或者 顺序队列(常用循环顺序队) 

//基本操作
//InitQueue(&Q)  DestoryQueue(&Q)  ClearQueue(&Q)  QueueLength(Q)  
//GetHead(Q, &e)  EnQueue(&Q, e)   DeQueue(&Q, &e) 还有将队列置空、遍历队列等操作 

//队列的顺序表示 ---- 用一维数组base[MAXQSIZE] 
#define MAXQSIZE 100   //最大队列长度
#define QElemType int //队列元素类型 
typedef struct{
	QElemType *base;  //初始化的动态分配存储空间
	int front;		 //头指针 
	int rear;		//尾指针 
}SqQueue;

//初始时, front = rear = 0
//元素x入队：base[rear] = x; rear++; 
//元素出队：y = base[front]; front++; 
//空队标志：front == rear 

//rear = MAXQSIZE时，发生溢出。真溢出(front = 0)  假溢出(front!=0) 
//解决假上溢的方法----引入循环队列 
//base[0]接在base[MAXQSIZE - 1]之后，若 rear+1 == MAXQSIZE，则令rear=0;
//实现方法：利用模(mode, C语言中：%)运算
//插入元素：Q.base[Q.rear] = x;  Q.rear = (Q.rear + 1) % MAXQSIZE;
//删除元素：X = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXQSIZE; 

//循环队列：循环使用为队列分配的存储空间 

//循环队列怎么区别栈满，栈空；两种情况都是front = rear;
//解决方案：1.另外设一个标志以区别队空、队满
//			2.另设一个变量,记录元素个数
//			3.少用一个元素空间  队空：front == rear  队满： (rear + 1) % MAXQSZIE == front 

//算法3.11 队列的初始化
Status InitQueue(SqQueue &Q){
	Q.base = new QElemType[MAXQSIZE];  //分配数组空间
	//Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
	if(!Q.base) exit(OVERFLOW); //存储分配失败 
	Q.front = Q.rear = 0; //头指针尾指针置为0，队列为空  
	return OK;
} 

//算法3.12 求队列的长度 
int QueueLength(SqQueue Q){
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
 
//算法3.13 循环队列入队
Status EnQueue(SqQueue &Q, QElemType e){
	if((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR; //队满溢出
	Q.base[Q.rear] = e; //新元素加入队尾 
	Q.rear = (Q.rear + 1) % MAXQSIZE; //队尾指针+1 
	return OK; 
}

//算法3.14 循环队列出队 
Status DeQueue(SqQueue &Q, QElemType &e){
	if(Q.rear == Q.front) return FALSE; //队空 
	e = Q.base[Q.front];  //保存队头元素 
	Q.front = (Q.front + 1) % MAXQSIZE; //队头指针+1 
	return OK; 
}  

//算法3.15  取队头元素
QElemType GetHead(SqQueue Q){
	if(Q.front !=  Q.rear) 		  //队列不为空 
		return Q.base[Q.front];   //返回队头指针元素的值，队头指针不变 
} 

int main(){
	SqQueue Q;
	InitQueue(*&Q);
	puts("初始化队列Q成功!");
	int Q_len = QueueLength(Q);
	cout<<"Q.base = "<<Q.base<<"  Q.front = "<<Q.front<<"  Q.rear = "<<Q.rear<<"  Q_len = "<<Q_len<<"\n";
	puts("请输入你想创建的队列元素个数：");
	int num;
	cin>>num;
	puts("---------------------------------------\n开始入队");
	for(int i = 1; i <= num; i++){
		cout<<"请输入第"<<i<<"个元素：";
		QElemType e;
		cin>>e;
		EnQueue(*&Q, *&e);
		Q_len = QueueLength(Q);
		printf("入队成功，此时Q_len = %d\n", Q_len);
	}
	printf("----------------------------------------\n开始出队\n");
	while(Q_len){
		QElemType e;
		DeQueue(*&Q, *&e);
		Q_len = QueueLength(Q);
		printf("出队中，%d 已出队，此时Q_len = %d\n", e, Q_len);
	}
	return 0;
}